837F - Prefix Sums - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
#define int ll

const int maxn = 200001;
int arr[maxn];
// 题目中的k。因为k一般用作循环变量，所以不作为变量名
int limit;
// A0的长度
int n;

// “龟速乘法”
int mxqmul(int a,int b) {
    if(b == 0) return 0;
    int r = mxqmul(a, b >> 1);
    r = min(r + r, limit);
    if(b & 1) return min(r + a, limit);
    return r;
}

// 矩阵乘法封装类
struct Matrix:vector<vector<int> > {
    Matrix __construct(int l = 0, int w = 0, int v = 0) {
        assign(l, vector<int>(w, v));
        return *this;
    }

    Matrix(int l = 0, int w = 0, int v = 0) {
        assign(l, vector<int>(w, v));
    }

    unsigned sizeL() const {
        return size();
    }

    unsigned sizeW() const {
        return empty() ? 0 : (*this)[0].size();
    }

    Matrix operator* (const Matrix &other) const {
        if(sizeW() != other.sizeL()) {
            return Matrix(0, 0, 0);
        }

        int l = sizeL(), w = other.sizeW(), p = sizeW();
        Matrix ret(l,w,0);

        for(int i = 0; i < l; i ++) {
            for(int j = 0; j < w; j ++) {
                for(int k = 0; k < p; k ++) {
                    ret[i][j] += mxqmul((*this)[i][k], other[k][j]);
                    ret[i][j] = min(ret[i][j], limit);
                }
            }
        }
        return ret;
    }
    Matrix operator *= (const Matrix &other) {
        *this = (*this)*other;
        return *this;
    }

    Matrix pow(int t) {
        if(t == 0) {
            Matrix ret(sizeL(), sizeL(), 0);
            for(int i = 0; i < sizeL(); i ++) {
                ret[i][i] = 1;
            }
            return ret;
        }
        if(t == 1) {
            return *this;
        }
        if(t == 2) {
            return (*this)*(*this);
        }
        Matrix tmp = pow(t / 2);
        if(t % 2 == 0)
            return tmp * tmp;
        else
            return (*this) * tmp * tmp;
    }

    Matrix pow_(int t) {
        *this = pow(t);
        return *this;
    }

    void oi_input() {
        for(int i = 0; i < sizeL(); i ++) {
            for(int j = 0; j < sizeW(); j ++) {
                scanf("%lld", &(*this)[i][j]);
            }
        }
    }

    void oi_output() {
        for(int i = 0; i < sizeL(); i ++) {
            for(int j = 0; j < sizeW(); j ++) {
                printf("%lld ", (*this)[i][j]);
            }
            printf("\n");
        }
    }
};

// 二分的check。如果Ap中存在大于等于limit的元素返回true，否则返回false
bool check(int p) {
    Matrix mt(n, n, 0);

    for(int i = 0; i < n; i ++) {
        for(int j = 0; j <= i; j ++) {
            mt[i][j] = 1;
        }
    }

    Matrix ar(n, 1, 0);
    for(int i = 0; i < n; i ++) {
        ar[i][0] = arr[i + 1];
    }

    ar = mt.pow(p) * ar;

    for(int i = 0; i < n; i ++) {
        if(ar[i][0] >= limit)
            return true;
    }
    return false;
}

// 删除前导0，返回删除后数列的长度
int unuqie(int *arr, int len) {
    int ptr = 0;
    for(int i = 1; i <= len; i ++) {
        if(arr[i] != 0 || ptr) {
            arr[++ ptr] = arr[i];
        }
    }
    return ptr;
}

// 功能相当于 (int)ceil((double)a/b)
// 用于A0的长度等于2的情况下。由于double的精度问题，并不能使用强转double并ceil的方法。
int ceilDiv(int a, int b) {
    return a / b + bool(a % b);
}

signed main() {
    scanf("%lld", &n);
    scanf("%lld", &limit);
    for(int i = 1; i <= n;i ++)
        scanf("%lld", &arr[i]);

    // 去除前导0
    n = unuqie(arr, n);

    // 判断 |A0| == 2
    if(n == 2) {
        printf("%lld\n", max(0ll, ceilDiv((limit - arr[2]), arr[1])));
        exit(0);
    }

    // 判断答案为0的情况（防止出现问题）
    for(int i = 1; i <= n; i ++) {
        if(arr[i] >= limit) {
            printf("0\n");
            exit(0);
        }
    }

    // 如果 |A0| >= 10，可以暴力迭代完成。
    if(n >= 10) {
        int cnt = 0;
        while(1) {
            cnt ++;
            for(int i = 1;i <= n; i ++) {
                arr[i] += arr[i - 1];
                if(arr[i] >= limit) {
                    printf("%lld\n", cnt);
                    exit(0);
                }
            }
        }
    }

    // 否则二分答案
    // 考虑二分边界的方法：
    //   如果check(mid)为true，那么mid值偏大或正好
    //     由于check(mid)为true，最终答案可能是mid，所以 r = mid (如果最终答案不可能是mid，取 r = mid - 1)
    //   如果check(mid)为false，那么mid值偏小
    //     最终答案不可能取mid，所以 l = mid + 1 (如果最终答案可能是mid，取 l = mid)
    // 随后考虑最容易死循环的情况，即 r - l == 1，来确定mid的取值
    //   如果令 mid = l+r - (l+r)/2，则此情况下mid = r：
    //     若check(mid) == true，那么执行 r = mid，即 r = r，此时二分范围没有变小，会造成死循环，所以应当令 mid = (l+r)/2
    int l = 0, r = 64356879284;
    while(l < r) {
        int mid = (l + r) / 2;
        if(check(mid)) {
            r = mid;
        }
        else {
            l = mid + 1;
        }
    }
    printf("%lld\n", l);
}